/**
 * 20\. 有效的括号
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 * - 左括号必须用相同类型的右括号闭合。
 * - 左括号必须以正确的顺序闭合。
 *
 * @example 输入：s = "()[]{}"
 * 输出：true
 *
 * 思路 栈
 * 把所有 {([ 符号入栈
 * 当 遇到 右侧符号 })] 开始进行 不出栈 匹配
 * 匹配失败 return false
 * 匹配成功 出栈
 * 当 栈 为空 时说明 是有效的括号字符串
 *
 * @see https://leetcode.cn/problems/valid-parentheses/
 *
 * @param {string} str
 */
function isValid(str: string) {
  const length = str.length
  if (length === 0) return false
  if (length % 2 > 0) return false

  /**
   * 左侧符号栈
   */
  const stack: string[] = []

  const match = function (left: string | undefined, right: string) {
    switch (right) {
      case ']':
        return left === '['
      case '}':
        return left === '{'
      case ')':
        return left === '('
      default:
        return false
    }
  }

  for (let i = 0; i < length; i++) {
    const s = str.charAt(i)
    // 当 s 为 右侧符号时 开始匹配
    if (s === ']' || s === '}' || s === ')') {
      // 取最后一个入栈值 不出栈
      if (match(stack[stack.length - 1], s)) {
        // 匹配到 出栈
        stack.pop()
      } else {
        return false
      }
    } else {
      // 左侧符号入栈
      stack.push(s)
    }
  }

  return stack.length === 0
}

console.log(isValid('{[]}'))
